Home Algorithm

# Insertion Sort

原理是逐一將原始資料加入已排序好資料中，並逐一與已排序好的資料作比較，找到對的位置插入。
平均時間複雜度為: O (n²)

PseudoCode
void insertionsort (int n, keytype S[]) {
    index i, j;
    keytype x;
    for (i=2; i<=n; i++) {
        x = S[i];
        j = i-1;
        while (j > 0 && S[j] > x) {
            S[j+1] = S[j];
            j--;
        }
        S[j+1] = x;
    }
}

# Selection Sort

原理是反覆從未排序數列中找出最小值，將它與左邊的數做交換。
平均時間複雜度為: O (n²)

PesudoCode
void selectionsort(int n, keytype S[]) {
    index i, j, smallest;
    for (i=1; i<=n-1; i++) {
        smallest = i;
        for (j=i+1; j<=n; j++) {
            if (S[j] < S[smallest]) smallest = j;
        }
        exchange S[i] amd S[smallest];
    }
}

# Merge Sort

原理是會先將原始資料分割成兩個資料列，接著再將兩個資料繼續分割成兩個資料列，依此類推，直到無法再分割，也就是每組都只剩下一筆資料時，再兩兩合併各組資料，合併時也會進行該組排序，每次排序都是比較最左邊的資料，將較小的資料加到新的資料列中，依此類推，直到最後合併成一個排序好的資料列為止。

# Quick Sort

原理是先從原始資料列中找一個基準值 (Pivot)，接著逐一將資料與基準值比較，小於基準值的資料放在左邊，大於基準值的資料放在右邊，再將兩邊區塊分別再找出基準值，重複前面的步驟，直到排序完為止。

PesudoCode
void quicksort(index low, index high) {
    index pivotpoint;
    if (high > low) {
        partition(low, high, pivotpoint);
        quicksort(low, pivotpoint - 1);
        quicksort(pivotpoint + 1, high);
    }
}

# Heap Sort

操作流程 (最大堆積為例):

  1. 將陣列轉換最大堆積 (Max Heap)
  2. 將 Root 與最後一個節點交換
  3. 將最後一個節點移除
  4. 將剩餘未排序完的節點重複 1~3 步驟，直到所有節點被移除，即完成排序。